The growing network of packet based routers and bridges used in the Internet and other packet networks in addition to the increased network speeds of routing packets, such as 10 Gigabits per second, as specified in Optical Carrier standard document OC-192, require more efficient handling of large databases having long lookup keys. Such efficient handling involves processing database table lookups at rates over 250 million searches per second (Msps), limiting memory footprint size of memory modules, and limiting the density of each individual memory module used. All of these requirements must be met at a reasonable cost and at low power consumption. When processing a packet through a router, large databases such as the Internet protocol traffic flow database (TDB) as well as the forwarding information database (FIB) represent major performance bottlenecks in the high speed Internet traffic routing application.
One current hardware approach for addressing these requirements consists of implementing a lookup circuit on a standard embedded dynamic random access memory (DRAM) on a single silicon integrated circuit device. DRAMs are convenient because they are relatively cheap and provide a high chip density at very low power since only one transistor and one capacitor are necessary to store one bit of information. With a typical lookup circuit based on a search algorithm implemented in logic circuits and a standard DRAM memory which holds a key database, multiple accesses to this memory are required. The number of accesses are typically dependent on the key size. Multiple accesses may unduly slow the lookup process, and thus, such methods may provide inadequate system performance in high speed networking applications.
Another hardware approach involves porting the typical lookup circuit to a ternary content addressable memory (TCAM) device. By doing so, a high speed lookup rate may be achieved. TCAMs usually operate in the range of 50–100 million searches per second which is several times the rate required for OC-192 or 10-Gigabit Ethernet carriers. TCAM devices may either be static or dynamic. A dynamic TCAM device may be of higher density and may consume less power than a TCAM static device.
However, unlike DRAM, a TCAM device requires approximately 6–16 transistors to store one bit of information, the number depending upon whether the device is designed based on a static or a dynamic memory cell. Since the current manufacturing technology and state of the art circuit design limits TCAM chips to 18 Megabits per chip, assuming 128k entries with a key size of 144 bits, a single TCAM chip may consume up to 300 million transistors, thus pushing the limits of the state of the art silicon manufacturing process. In addition, the TCAM circuit design based on a dynamic random access memory cell approach represents a considerable manufacturing challenge and is not in common use. Given that a typical TDB table contains about 512k 256-bit entries, and the cost of a TCAM device is typically multiple times higher than a DRAM device, the cost of a TCAM based approach may be prohibitive.
The typical lookup circuit approach involves a hashing circuit where incoming packet data or a packet header is converted to a single non-unique scalar identifier. Due to the non-uniqueness of the hashing identifier, typical hashing circuits may not handle the case where the packet data maps to the same identifier and the same memory location. As discussed in PCT Patent Application No. WO 01/78309 A2, published 18 Oct. 2001 entitled “A Method and Apparatus for Wire-Speed Application Layer Classification of Data Packets”, a typical hashing circuit may be expanded so that when a mapping conflict exists due to duplicate keys, redundant memory locations are preserved which are addressed through the same hashing identifier. However, in expanding a hashing circuit to handle redundancy in this manner, the resulting memory footprint expands proportionately for each defined hash key. Further, since hashing keys are scalar and not unique, if redundant memory locations are fully populated for a specific hashing key, remapping of existing data within a table currently cannot be addressed.
Among its various aspects, the present invention recognizes that a memory apparatus implemented in a hardware circuit which provides key searching speeds that are near or exceed the speeds of a TCAM approach while based on less expensive DRAM technology is needed to address the ever expanding speeds and capacity of today's Internet packet routers.